package fun.coding.leetcode;

public class ReorderList {

	public static void main(String[] args) {
		ReorderList instance = new ReorderList();
		int[] a1 = {1, 2, 3, 4};
		ListNode l1 = LeetCodeHelpers.buildLinkedList(a1);
		instance.reorderList(l1);
		LeetCodeHelpers.printList(l1);
	}

	// Given {1,2,3,4, 5, 6}, reorder it to {1,6,2,5,3,4}.
	// Break it into two lists and then merge
	public void reorderList(ListNode head) {
		if (head == null || head.next == null) return;
		
		ListNode mid = findMiddle(head);
		ListNode newHead = reverseList(mid.next);
		mid.next = null;
		
		ListNode dummy = new ListNode(-1);
		ListNode cur = dummy;
		
		while (head != null && newHead != null) {
			cur.next = head;
			head = head.next;
			
			cur.next.next = newHead;
			cur = newHead;
			newHead = newHead.next;
		}
		
		if (head != null) {
			cur.next = head;
		}
		
		if (newHead != null) {
			cur.next = newHead;
		}
		
		head = dummy.next;
	}
	
	// This is the easiest way to reverse a linkedlist
	public ListNode reverseList(ListNode head) {
		ListNode dummy = new ListNode(-1);
		ListNode cur = head;
		
		while (cur != null) {
			ListNode next = cur.next;
			cur.next = dummy.next;
			dummy.next = cur;
			cur = next;
		}
		return dummy.next;
	}
	
	public ListNode findMiddle(ListNode head) {
		if (head == null) return head;
		
		ListNode slow = head;
		ListNode fast = head.next;
		
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		
		return slow;
	}
	////////***************************//
	
	
	// Given a singly linked list L: L0→L1→…→Ln-1→Ln,
	// reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
	public void reorderListNotInPlace(ListNode head) {
		if (head == null) return;
		
		ListNode dummy = new ListNode(-1);
		helper(head, dummy);
	}
	
	// Recursion solution will time out, since it is not inplace, 
	// in-place means constant space wile recursion uses O(lgn) stack space
	public void helper(ListNode head, ListNode dummy) {
		if (head == null || head.next == null) {
			dummy.next = head;
			head.next = null;
			return;
		}
		
		ListNode dummyHead = new ListNode(-1);
		dummyHead.next = head;
		
		ListNode pre = dummyHead;
		ListNode cur = pre.next;
		
		while (cur != null && cur.next != null) {
			pre = cur;
			cur = cur.next;
		}
		
		dummy.next = head;
		ListNode newHead = head.next;
		head.next = cur;
		
		if (head != pre) {
			pre.next = null;
		}
		
		dummy = cur;
		
		helper(newHead, dummy);
	}
}
